package com.yun.algorithmproblem.leetcodenotoptimized;

import java.util.HashMap;

public class Leetcode2537 {

	public static void main(String[] args) {
		Leetcode2537 obj = new Leetcode2537();
		obj.countGood(new int[] {3,1,4,3,2,2,4}, 2);
	}

	public long countGood(int[] nums, int k) {
		HashMap<Integer, Integer> map = new HashMap<>();
		int n = nums.length;
		int p = 0, q = 0;
		int cnt = 0;
		long ans = 0;

		while (q < n) {
			// 扩展窗口
			map.put(nums[q], map.getOrDefault(nums[q], 0) + 1);
			if (map.get(nums[q]) > 1) {
				cnt += map.get(nums[q]) - 1;
			}

			// 当cnt满足k时，计算结果
			while (cnt >= k) {
				ans += n - q;  // 所有[nums[p], ..., nums[q]]的组合都符合条件
				// 收缩窗口
				map.put(nums[p], map.get(nums[p]) - 1);
				if (map.get(nums[p]) > 0) {
					cnt -= map.get(nums[p]);
				}
				p++;
			}

			// 移动右指针
			q++;
		}

		return ans;
	}
}
